#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int tempt [N];
typedef int lin;
class Sort {
public:
	lin arr[12] = { 8,9,4,2,7,4,1,3,9,5,6,4 };
public:
	
	void print(lin arr[], int n)
	{
		for (int i = 0; i < n; i++)
		{
			cout << arr[i]<<",";

		}
	}
	void popsort(lin arr[], int n)
	{
		for (int i = 0; i < n-1; i++)
		{			
			for (int j = 0; j < n-1-i; j++)
			{
				if (arr[j] > arr[j + 1])
				{
					//lin arr[12] = { 8,9,4,2,7,4,1,3,9,5,6,4 };
					int tempt = arr[j];
					arr[j] = arr[j + 1];				
				arr[j + 1] = tempt;	

				}
			}

		}
		print(arr, n);	
	}
	void choicesort(lin arr[], int n)
	{	
		//lin arr[12] = { 8,9,4,2,7,4,1,3,9,5,6,4 };
		for (int i = 0; i < n - 1; i++)
		{
			int t = 0;
			int max = arr[0];
			for (int j = 0; j < n - i; j++)
			{
				
				if (arr[j] > max)
				{
					max = arr[j];
					t = j;
				}

			}

			int tempt = arr[t];
			arr[t] = arr[n - i - 1];
			arr[n - i - 1] = tempt;
		}

		print(arr, n);
	}
	void insort( lin arr[],int n)
	{
		for (int i = 1; i < n; i++)
		{
			for (int j = i; j > 0; j--)
			{
				//lin arr[12] = {9 8,,4,2,7,4,1,3,9,5,6,4 };
				if (arr[j] < arr[j - 1])
				{
					int tempt = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = tempt;
				}
			}
		}
		print(arr, n);
	}
	void choicesort1(int arr[], int n)
	{
		for (int i = 0; i < n - 1; i++)
		{
			int k = 0;
			int j = 0;
			for (j ; j < n - i; j++)
			{
				if (arr[k] < arr[j])
				{
					k = j;
				}
				

			}

			int tempt = arr[n - i-1];
			arr[n - i-1] = arr[k];
			arr[k] = tempt;
		}
		print(arr, n);
	}
	void insort1(int arr[], int n)
	{
		int tempt=-1;
		
		for (int i = 1; i < n; i++)
		{
			//lin arr[12] = {9 8,,4,2,7,4,1,3,9,5,6,4 };
			if (arr[i] < arr[i - 1])
				tempt = arr[i];
			int j;
			for (j = i - 1; j >=0&&arr[j] > tempt;j--)
				
				arr[j+1] = arr[j];
			if(tempt!=-1)
			arr[j + 1] = tempt;
		}
		print(arr, n);
	}
	void quick_sort(int q[], int l, int r)
	{
		if (l >= r)
			return;
		int x = q[(l + r) / 2];
		int i = l - 1;
		int j = r + 1;
		while (i < j)
		{
			do i++; while (q[i] < x);
			do j--; while (q[j] > x);
			if (i < j)
				swap(q[i], q[j]);
		}
		quick_sort(q, l, j);
		quick_sort(q, j + 1, r);
		return;
	}
	void merga_sort(int a[], int r, int l)
	{
		if (l >= r)
			return;
		int mid = l + r >> 1;
		merga_sort(a, l, mid);
		merga_sort(a, mid + 1, r);
		int k = 0, i = l, j = mid + 1;
		while (i <= mid && j <= r)
		{
			if (a[i] >= a[j])tempt[k++] = a[j++];
			else
				tempt[k++] = a[i++];
		}
		while (i <= mid)tempt[k++] = a[i++];
		while (j <= r)tempt[k++] = a[j++];
		for (int i = l, j = 0; i <= r; i++, j++)a[i] = tempt[j];
	}

};
int main()
{
	Sort a;
	//a.popsort(a.arr,12);
	//a.choicesort1(a.arr, 12);
	a.insort1(a.arr, 12);


	return 0;
}
